package com.gxc.array;

import java.util.Stack;


/**
 * 给定不含重复值的数组arr，找到每个i位置左边和右边距离i最近的且值比i小的位置(没有返回-1)，返回所有的位置信息。
 * arr = {3, 4, 1, 5, 6, 2, 7}
 * 输出：
    -1 2
    0 2
    -1 -1
    2 5
    3 5
    2 -1
    5 -1
 */
public class GetNearLess {

    public static void main(String[] args) {
        int[] nums = {3, 4, 1, 5, 6, 2, 7};
        int[][] list = handle(nums);

        for (int i = 0; i < list.length; i++) {
            for (int j = 0; j < list[i].length; j++) {
                System.out.print(list[i][j] + " ");
            }
            System.out.println(" ");
        }
    }

    //单调栈
    private static int[][] handle(int[] nums) {
        int[][] arr = new int[nums.length][2];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[i]<nums[stack.peek()]) {
                Integer pop = stack.pop();
                arr[pop][1] = i;
                if (stack.isEmpty()) {
                    arr[pop][0] = -1;
                } else {
                    arr[pop][0] = stack.peek();
                }
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            Integer pop = stack.pop();
            arr[pop][1] = -1;
            if (stack.isEmpty()) {
                arr[pop][0] = -1;
            } else {
                arr[pop][0] = stack.peek();
            }
        }
        return arr;
    }
}
